class TrieNode:
    def __init__(self):
        self.children = [None] * 26 # 子节点指针数组
        self.is_end = False         # 标记是否为单词结尾

"""
方法：实现前缀树（字典树）数据结构，用于高效存储和检索字符串集合

Args:
    - word: str, 要插入或搜索的单词
    - prefix: str, 要搜索的前缀

Returns:
    - insert: None, 无返回值
    - search: bool, 如果单词存在返回True，否则返回False
    - startsWith: bool, 如果前缀存在返回True，否则返回False

Time:
    - insert: O(n), n为单词长度
    - search: O(n), n为单词长度
    - startsWith: O(n), n为前缀长度

Space:
    - O(m*n), m为字符集大小（26个字母），n为所有单词的总长度
"""

class Trie:

    def __init__(self):
        self.root = TrieNode()  # 根节点

    def insert(self, word: str) -> None:
        node = self.root
        for c in word:
            idx = ord(c) - ord('a')  # 计算字母索引（0~25）
            if not node.children[idx]:
                node.children[idx] = TrieNode() # 创建新节点
            node = node.children[idx]
        node.is_end = True # 标记单词结尾

    def find(self, word: str) -> int:
        node = self.root
        for c in word:
            idx = ord(c) - ord('a')
            if not node.children[idx]:
                return 0
            node = node.children[idx]
        # 走过同样的路（2=完全匹配，1=前缀匹配）
        return 2 if node.is_end else 1

    def search(self, word: str) -> bool:
        return self.find(word) == 2

    def startsWith(self, prefix: str) -> bool:
        return self.find(prefix) != 0
        


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)